W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Bajtazar prosi Cię o pomoc przy obrabianiu pewnego drzewa . Jest to drzewo binarne, którego liście mają pewne etykiety (etykiety mogą się powtarzać). Dla każdej etykiety Bajtazar chciałby zobaczyć drzewo o następujących własnościach:
Pomóż Bajtazarowi i napisz program, który dla każdej etykiety występującej w drzewie wyznaczy drzewo .
Napisz program, który:
W każdym wierszu standardowego wejścia opisany jest dokładnie jeden wierzchołek drzewa . Drzewo to jest zapisane w kolejności pre-order. W pierwszym wierszu opisu drzewa (zarówno całego, jak i każdego poddrzewa) znajduje się opis korzenia, następnie (jeśli korzeń nie jest liściem) opis lewego poddrzewa, po czym opis prawego poddrzewa. Jeśli mamy do czynienia z wierzchołkiem wewnętrznym, w wierszu znajduje się pojedyńczy znak gwiazdki '*'. W przypadku liścia, w wierszu znajduje się jego etykieta. Jest to niepusty napis, który może zawierać wyłącznie małe litery od 'a' do 'z'. Łączna długość wszystkich etykiet będzie nie większa niż (każdą etykietę liczymy tyle razy, ile występuje na wejściu).
Wierzchołki drzewa numerowane są zgodnie z ich kolejnością występowania na wejściu, poczynając od 1 (czyli numer wierzchołka równa się numerowi wiersza).
Twój program powinien wypisać na standardowym wyjściu opisy wszystkich drzew , w kolejności leksykograficznej etykiet. Opis każdego drzewa powinien mieścić się w jednym wierszu. Podobnie jak na wejściu ma to być opis pre-order, jednak wypisywać należy numery wierzchołków, które są w drzewie. Zatem opis drzewa to numer korzenia, po czym (jeśli to nie liść) opisy lewego i prawego poddrzewa.
Dla danych wejściowych:
* * a ab * * c ab * c c
poprawną odpowiedzią jest:
3 1 4 8 5 7 9 10 11
Autor zadania: Paweł Parys.